Псевдорешения несовместных систем линейных уравнений. Метод наименьших квадратов

**Псевдорешение** системы линейных уравнений $A\mathbf{x} = \mathbf{b}$ - это вектор $\mathbf{x}_{0}$, минимизирующий расстояние между векторами $A\mathbf{x}$ и $\mathbf{b}$ План поиска псевдорешений таков: - найти ортогональную проекцию $\mathbf{b}_{S}$ вектора $\mathbf{b}$ на образ $S$ линейного отображения $\mathbf{x} \mapsto A\mathbf{x}$ (т.е на пространство, порождённое столбцами $A$) - решить совместную систему $A\mathbf{x} = \mathbf{b}_{S}$ В реальных задачах ранг матрицы $A$ равен числу неизвестных, а потому система $A\mathbf{x} = \mathbf{b}_{S}$ имеет единственное решение, а значит имеется **единственное** псевдорешение исходной системы $A\mathbf{x} = \mathbf{b}$ Если псевдорешение не единственно, то обычно интересуются псевдорешением наименьшей длины (**нормальное** псевдорешение).

Пусть $A$ - $k \times n$-матрица над $\mathbb{R}$, $\mathcal{A}: x \mapsto Ax$ ($\mathbb{R}^{n} \to \mathbb{R}^{k}$), $S = \mathrm{Im}~\mathcal{A}$. Тогда для произвольного вектора $b \in \mathbb{R}^{k}$ системы линейных уравнений $Ax = b_{S}$ и $A^{T}Ax = A^{T}b$ равносильны. Таким образом, $x \in \mathbb{R}^{n}$ - псевдорешение $Ax = b \iff$ $x$ - решение системы $A^{T}Ax = A^{T}b$

$\Large\implies$ $S = \mathrm{Im}~\mathcal{A}$ порождается столбцами $A$, а значит строками $A^{T}$. Из ортогонального разложения $\mathbb{R}^{k}$ относительно $S$ имеем: $b = b_{S} + b^{\perp}$. Умножим равенство слева на $A^{T}$ и вспомним формулу скалярного произведения в ортонормированном базисе ($\mathbf{u}\mathbf{v} = [\mathbf{u}]^{T}[\mathbf{v}]$): $$A^{T}b = A^{T}(b_{S} + b^{\perp}) = A^{T}b_{S} + A^{T}b^{\perp} = A^{T}b_{S} ~~~~~(*)$$ так как $b^{\perp}$ - ортогонален всем векторам из $S$ Тогда, если $x \in \mathbb{R}^{n}$ - решение системы $Ax = b_{S}$, то: $$A^{T}Ax = A^{T}b_{S} \overbrace{ = }^{ (*) } A^{T}b$$ $\Large\impliedby$ Пусть $x \in \mathbb{R}^{n}$ - решение системы $A^{T}Ax = A^{T}b$. Возьмём произвольный $y \in \mathbb{R}^{n}$ и перемножим вектора $Ay$ и $Ax - b_{S}$: $$(Ay)^{T}(Ax - b_{S}) = y^{T}A^{T}(Ax - b_{S}) = y^{T}(A^{T}Ax - A^{T}b_{S}) \overbrace{=}^{ (*) } y^{T}(A^{T}Ax - A^{T}b) = 0$$ Итак, вектор $Ax - b_{S}$ ортогонален любому вектору из $S$, в частности, самому себе. Отсюда $Ax - b_{S} = 0$ и $Ax = b_{S}$ $~~~\square$

1. Если ранг $k \times n$-матрицы $A$ равен $n$, то $n \times n$-матрица $A^{T}A$ будет обратимой (***упражнение***). В этом случае при любой правой части $b \in \mathbb{R}^{k}$ система $Ax = b$ имеет единственное псевдорешение, для которого есть простая формула: $$x = (A^{T}A)^{-1}A^{T}b$$ 2. Метод наименьших квадратов работает и над полем $\mathbb{C}$. Единственное отличие состоит в том, что необходимо заменить транспонирование на **эрмитово сопряжение**: $$A^{*}Ax = A^{*}b$$ $$A = (a_{ij})_{k\times n} \implies A^{*} := \overline{(A^{T})} = (\overline{a_{ji}})_{n\times k}$$